//
//  GameAlgorithm.cpp
//  PencilParkour
//
//  Created by longlingxiu on 14-7-30.
//
//

#include "GameAlgorithm.h"


/*Algorithm*/
bool Algorithm::rectBoxColl( CCRect box1, CCRect box2 ){
    
    return box1.intersectsRect( box2 );
}


QuadTree::QuadTree( int pLevel, CCRect _bounds ){
    
    level = pLevel;
    bounds = _bounds;
    
    objects = CCArray::create();
    CC_SAFE_RETAIN( objects );
    
}

QuadTree::~QuadTree(){
    
}

/**
  1 0
  2 3
 
 **/
int QuadTree::getIndex( CCRect box ){
    
    int index = -1;
    
    bool isTop = box.getMinY() > bounds.getMidY();
    bool isBottom = box.getMaxY() < bounds.getMidY();
    
    if ( box.getMaxX() < bounds.getMidX() ) { // left
        
        if ( isTop ) { // left top
            index = 1;
        }else if ( isBottom ){ // left bottom
            index = 2;
        }
        
    }else if ( box.getMinX() > bounds.getMidX() ){  // right
        if ( isTop ) { // right top
            index = 0;
        }else if ( isBottom ){ // right bottom
            index = 3;
        }
    }
    
    return index;
}

/**
 
    切割出四个子节点
 **/
void QuadTree::split(){
    
//    CCLOG( "拆分" );
    
    float subWidth = bounds.size.width / 2 ;
    float subHeight = bounds.size.height / 2 ;
    
    float x = bounds.getMinX();
    float y = bounds.getMaxY();
    
    QuadTree node0( level + 1, CCRectMake( x+subWidth, y, subWidth, subHeight));
    QuadTree node1( level + 1, CCRectMake( x, y, subWidth, subHeight));
    QuadTree node2( level + 1, CCRectMake( x, y - subHeight, subWidth, subHeight));
    QuadTree node3( level + 1, CCRectMake( x + subWidth, y - subHeight, subWidth, subHeight));
    
    nodes.push_back( node0 );
    nodes.push_back( node1 );
    nodes.push_back( node2 );
    nodes.push_back( node3 );
    
}


/**
 
    测试插入节点
 
 **/
void QuadTree::insert(cocos2d::CCDictionary *dic){
    float x = dic->valueForKey( "x" )->floatValue();
    float y = dic->valueForKey( "y" )->floatValue();
    float width = dic->valueForKey( "width" )->floatValue();
    float height = dic->valueForKey( "height" )->floatValue();
    
    CCRect box = CCRectMake(x, y, width, height);
    
    // 有子节点 
    if ( !nodes.empty() ) {
        int index = getIndex( box );
        if ( index != -1) {
            nodes[index].insert(dic);
            return;
        }
    }
    
    objects->addObject( dic );

    if ( objects->count() > MAX_OBJECTS && level < MAX_LEVEL ) {
        split();
        int loop = 0;
        while ( loop < objects->count() ) {
            
            CCLOG( "loop:%i",loop);
            CCLOG( "size:%i",objects->count());
            
            CCDictionary* dic = (CCDictionary*)objects->objectAtIndex( loop );
            
            float _x = dic->valueForKey( "x" )->floatValue();
            float _y = dic->valueForKey( "y" )->floatValue();
            float _width = dic->valueForKey( "width" )->floatValue();
            float _height = dic->valueForKey( "height" )->floatValue();
            
            
            int index = getIndex( CCRectMake(_x, _y, _width, _height));
            
            if ( index != -1) {
                
                nodes[index].insert( (CCDictionary*)objects->objectAtIndex(loop));
                
                objects->removeObjectAtIndex(loop);
                
            }else{
                
                loop++;
                
            }
            
        } //  end  while
    } //    end if
    
    
} // end insert



/**
 
    插入 充值精灵版本
 **/
void QuadTree::insert( CCSprite* sprite ){
    
    // 有子节点
    if ( !nodes.empty() ) {
        int index = getIndex( sprite->boundingBox() );
        if ( index != -1) {
            nodes[index].insert( sprite );
            return;
        }
    }
    
    objects->addObject( sprite );
    
    if ( objects->count() > MAX_OBJECTS && level < MAX_LEVEL ) {
        split();
        int loop = 0;
        while ( loop < objects->count() ) {
            
            CCSprite* sp = (CCSprite*)objects->objectAtIndex(loop);
            
            int index = getIndex( sp->boundingBox() );
            
            if ( index != -1) {
                
                nodes[index].insert( (CCSprite*)objects->objectAtIndex(loop));
                
                objects->removeObjectAtIndex(loop);
                
            }else{
                
                loop++;
                
            }
            
        } //  end  while
    } //    end if
    
    
}

/**
 
    返回CCArray的版本
 **/
CCArray* QuadTree::retrive( CCSprite* sprite ){
    
    
    int index = getIndex( sprite->boundingBox() );
    
    CCArray* array = CCArray::create();
    
    if ( index != -1 && !nodes.empty() ) {
        
        CCArray* arr = nodes[index].retrive( sprite );
        array->addObjectsFromArray( arr );
<<<<<<< HEAD
=======
        
        return array;
>>>>>>> b89f741c971ee9ecd1603718fb74ceabda05bef7
    }
    
    array->addObjectsFromArray( objects);
    
    return array;
}

/**
 
     返回碰撞矩形版本
 
 **/
std::vector<CCSprite*> QuadTree::getCollVector( CCSprite* sprite ){
    
    
    int index = getIndex( sprite->boundingBox() );
    
    std::vector<CCSprite*> vect;
    
    if ( index != -1 && !nodes.empty() ) {
        std::vector<CCSprite*> _v = nodes[index].getCollVector(sprite);
        vect.insert(vect.end(), _v.begin(), _v.end());
    }
    
    CCObject* obj = NULL;
    CCARRAY_FOREACH(objects,obj ){
        
        CCSprite* sp = (CCSprite*)obj;
        vect.push_back( sp );
    }

    
    return vect;
}
/**
 
 
 **/
/**
 *   获取碰撞的Vector
 *
 *  @param dic
 *
 *  @return
 */
std::vector<CCDictionary*> QuadTree::getCollVector( CCDictionary* dic ){
    
    float x = dic->valueForKey( "x" )->floatValue();
    float y = dic->valueForKey( "y" )->floatValue();
    float width = dic->valueForKey( "width" )->floatValue();
    float height = dic->valueForKey( "height" )->floatValue();
    
    int index = getIndex( CCRectMake(x, y, width, height));
    
    std::vector<CCDictionary*> vect;
    
    if ( index != -1 && !nodes.empty() ) {
        std::vector<CCDictionary*> _v = nodes[index].getCollVector(dic);
        vect.insert(vect.end(), _v.begin(), _v.end());
    }
    
    CCObject* obj = NULL;
    CCARRAY_FOREACH(objects,obj ){
        
        CCDictionary* dic = (CCDictionary*)obj;
        vect.push_back( dic );
    }
    
    return vect;
}


/**
 *  清空list
 */
void QuadTree::clear(){
    
    for (int i = 0 ; i < nodes.size(); i++ ) {
        nodes[i].clear();
    }
    
    objects->removeAllObjects();
    
    CC_SAFE_RELEASE_NULL( objects );
    
}













